1. Field of the Invention
The present invention relates to communications networks, and, more specifically, to mechanisms for calculating recovery paths in mesh communication networks.
2. Description of the Related Art
A mesh communication network includes a set of nodes interconnected by communication links. A path in a mesh network is a set of one or more links connecting a source node to a destination node possibly through one or more intermediate “transit” nodes. Mesh networks that are able to recover automatically from the failure of at least one node or link along paths in the network are considered to be “protected” networks. Recovery mechanisms for such protected networks can be either path-based or link-based.
Path-based recovery is the process of recovering from a failure of one of the links or nodes in a path from a source node to a destination node by rerouting traffic for the entire path along a recovery path. In path-based recovery, the recovery path shares only the source and destination nodes with the original path.
Link-based recovery, on the other hand, is the process of recovering from a single link/node failure by rerouting traffic around the failure using a link-detour path, without rerouting the entire path. A link-detour path is that portion of a link-based recovery path that corresponds to the failure. In many instances, the recovery path for link-based recovery from the failure of a single link is identical to the original path with the exception of the failed link, which is replaced by two or more new links connecting one or more new nodes.
Extensive work has been done on calculating primary paths and their recovery paths (also known as protection paths) for networks that employ path-based recovery (see, e.g., Doshi 58-10-27-19-36). Some work has also been done on calculating link-detour paths for links in primary paths for networks that employ link-based recovery.